P5504 [JSOI2011]柠檬
可以看出,选出区间的端点大小必须相同,不然可以将一端分在其他区间里,答案不会更劣。
令 dpi 表示前 i 个贝壳能得到的最大柠檬数, posi 表示第 i 个贝壳是第几个这种颜色的贝壳。
那么有转移:
P4072 [SDOI2016]征途
dp[i][j]=min(dp[i−1][k]+(Sumj−Sumk)2) (0≤k<j)
CF815C Karen and Supermarket
因为使用优惠劵就必须买这件商品,我们可以将优惠劵的关系看成一棵树。
令 dp[u][i][0/1] 表示 以 u 为根的子树 , 购买 i 件商品 , u 是否使用优惠劵的最小花费。
边界条件:dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]−d[u]
0%